package exams.dp;

import java.util.*;


public class LCSSolution {
    class Node {
        int i;
        int j;
        int dpv;
        public Node(int i, int j, int dpv) {
            this.i = i;
            this.j = j;
            this.dpv = dpv;
        }
    }

    /**
     * 最长公共子序列(二)
     */
    public String LCS (String s1, String s2) {
        // write code here
        // 缓存所有相同的元素的坐标以及dp值
        List<Node> rsList = new ArrayList<>();
        String[] sa1 = s1.split("");
        String[] sa2 = s2.split("");
        // dp表
        int[][] dpArray = new int[sa1.length + 1][sa2.length + 1];
        //记录最大dp值
        int maxdp = 0;

        // 构建dp表，以及找到所有相同元素并缓存坐标及dp值
        for(int i=1;i<=sa1.length;i++) {
            for(int j=1; j<= sa2.length; j++) {
                if(sa1[i - 1].equals(sa2[j - 1])) {
                    int v = dpArray[i - 1][j - 1] + 1;
                    rsList.add(new Node(i - 1, j - 1, v));
                    dpArray[i][j] = v;
                    maxdp = Math.max(maxdp, v);
                } else {
                    dpArray[i][j] = Math.max(dpArray[i][j-1], dpArray[i-1][j]);
                }
            }
        }
        if(maxdp == 0) {
            return "-1";
        }

        // 从所有相同元素的列表中选取最长子序列
        Node[] res = new Node[maxdp];
        ListIterator<Node> listIterator = rsList.listIterator(rsList.size());
        while(listIterator.hasPrevious()) {
            Node cur = listIterator.previous();
            if(maxdp == cur.dpv) {
                if (cur.dpv == res.length) {
                    res[cur.dpv - 1] = cur;
                    maxdp --;
                } else {
                    // 保证只取左上的元素
                    if(cur.i < res[cur.dpv].i && cur.j < res[cur.dpv].j) {
                        res[cur.dpv - 1] = cur;
                        maxdp --;
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0;i<res.length;i++) {
            sb.append(sa1[res[i].i]);
        }

        return sb.toString();
    }

    /**
     * 最长公共子串
     * */
    public String LCStr (String str1, String str2) {
        // write code here
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
        int max = 0;
        int maxIndex = 0;

        for(int i=1; i<=str1.length(); i ++) {
            for(int j = 1; j <= str2.length(); j++) {
                if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = 0;
                }

                if(dp[i][j] > max){
                    max = dp[i][j];
                    maxIndex = i - 1;
                }
            }
        }

        return str1.substring(maxIndex - max + 1, maxIndex + 1);
    }

    /**
     * 最长上升子序列(一)
     *
     * 给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。
     * 所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。
     * 我们定义一个序列是严格上升的，当且仅当该序列不存在两个下标i和j满足i<j且arri≥arrj。
     * 数据范围：0≤n≤1000
     * 要求：时间复杂度O(n2)， 空间复杂度O(n)
     * */
    public int LIS (int[] arr) {
        // write code here
        if(arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        int res = 1;
        Arrays.fill(dp, 1);
        for(int i=1; i<arr.length; i++) {
            for(int j =0; j<i; j++) {
                if(arr[j] < arr[i] && dp[i] < dp[j] + 1) {
                    dp[i] = dp[j] + 1;
                    res = Math.max(res,dp[i]);
                }
            }
        }


        return res;
    }

    /**
     * 最长回文子串
     *
     * 对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。
     *
     * 数据范围：1≤n≤1000
     * 要求：空间复杂度O(1)，时间复杂度O(n2)
     * 进阶: 空间复杂度O(n)，时间复杂度O(n)
     *
     * 输入：
     * "ababc"
     * 返回值：
     * 3
     * 说明：
     * 最长的回文子串为"aba"与"bab"，长度都为3
     *
     * */
    public int getLongestPalindrome (String A) {
        // write code here
        if(A.length() < 2) {
            return 1;
        }

        int max = 0;
        for(int i=0; i < A.length() - 1; i++) {
            max = Math.max(max, Math.max(getLength(A, i, i), getLength(A, i, i + 1)));
        }

        return max;
    }

    private int getLength(String A, int l, int r) {
        while(l>=0 && r < A.length() && A.charAt(l) == A.charAt(r)) {
            l--;
            r++;
        }

        return r - l + 1 - 2;
    }

    /**
     * 数字字符串转化成IP地址
     *
     * 现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。
     * 例如：
     * 给出的字符串为"25525522135",
     * 返回["255.255.22.135", "255.255.221.35"]. (顺序没有关系)
     *
     * 数据范围：字符串长度0≤n≤12
     * 要求：空间复杂度O(n!),时间复杂度O(n!)
     *
     * 注意：ip地址是由四段数字组成的数字序列，格式如 "x.x.x.x"，其中 x 的范围应当是 [0,255]。
     * */
    public ArrayList<String> restoreIpAddresses (String s) {
        // write code here
        ArrayList<String> res = new ArrayList<>();
        if(s.length() < 4) {
            return res;
        }
        for(int p1=0;p1<=2;p1++) {
            String sp1 = s.substring(0, p1 + 1);
            if(!isValidIPNum(sp1)) {
                break;
            }
            for(int p2=p1 + 1; p2<=p1 + 3 && p2 < s.length() - 2; p2 ++) {
                String sp2 = s.substring(p1+1, p2 + 1);
                if(!isValidIPNum(sp2)) {
                    break;
                }
                for(int p3=p2 + 1; p3<=p2 + 3 && p3<s.length() - 1; p3++) {
                    String sp3 = s.substring(p2+1, p3 + 1);
                    String sp4 = s.substring(p3 + 1, s.length());
                    if(!isValidIPNum(sp3)) {
                        break;
                    }
                    if(isValidIPNum(sp4)) {
                        res.add(String.join(".", sp1, sp2, sp3, sp4));
                    }
                }
            }
        }

        return res;
    }

    private boolean isValidIPNum(String s) {
        return !s.isEmpty() && !(s.length() > 1 && s.startsWith("0")) && Integer.valueOf(s).intValue() <= 255;
    }


    /**
     * 补中树
     * 1 2 3 4 5 6 7 8 9 10
     * 删掉某些树
     * 1 0 3 0 4 0 5 0 6 7 8 0 10
     * 补k颗树时，最长连续子串长度
     * 转换求成包含k个_的最长连续子序列问题
     * */
    public int getLength(int[] arr, int k) {
        int p1 = 0;
        int countK = 0;
        int res = 0;
        for(int p2=0; p2 < arr.length; p2++) {
            if(arr[p2] == 0) {
                countK++;
            }
            while(countK > k) {
                if(arr[p1] == 0) {
                    countK --;
                }
                p1++;
            }
            res = Math.max(res, p2 - p1 + 1);
        }
        return res;
    }
}